// https://www.lintcode.com/problem/longest-palindrome/

public class Solution {
    /**
     * @param s: a string which consists of lowercase or uppercase letters
     * @return: the length of the longest palindromes that can be built
     */
    public int longestPalindrome(String s) {
        // write your code here
        int ret = 0;
        boolean odd = false; // 是否奇数
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); ++i) {
            Character c = s.charAt(i);
            if (!map.containsKey(c)) {
                map.put(c, 0);
            }
            map.put(c, map.get(c) + 1);
        }
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            int v = entry.getValue();
            if ((v % 2) == 0) {
                ret += v;
            } else {
                odd = true; // 处理奇数，最后要额外加1。
                if (v > 1) {
                    ret += (v - 1);
                }
            }
        }
        if (odd) {
            return ret + 1;
        }
        return ret;
    }
}